#include <iostream>

using namespace std;

struct Node {
public:
	int data;
	Node* next;
};

class SingleLinkedList {
public:
	Node* pHead;

	//constructor
	SingleLinkedList() {
		pHead = NULL;
	}

	void prepend(int data) {
		Node* pNew = new Node();
		pNew->data = data;
		pNew->next = pHead;
		pHead = pNew;
	}

	void display() {
		if (pHead == NULL)
			cout << "List is NULL" << endl;
		else {
			Node* pt = pHead;
			while (pt != NULL) {
				if (pt->next == NULL)
					cout << pt->data << " -> NULL";
				else
					cout << pt->data << " -> ";
				pt = pt->next;
			}
		}

		cout << endl;
	}

	void insert(int data, int index) {
		cout << "Insert " << data << " at pos : " << index << endl;
		if (index == 0)
			prepend(data);
		else {
			Node* pNew = new Node();
			pNew->data = data;
			pNew->next = NULL;
			Node*pt = pHead;
			int c = 0;
			while (c < (index - 1)) {
				pt = pt->next;
				c++;
			}
			Node *ptNext = pt->next;
			pt->next = pNew;
			pNew->next = ptNext;
		}
	}

	Node* search(int target) {
		if (pHead == NULL)
			return NULL;
		else {
			Node* pt = pHead;
			while (pt != NULL) {
				if (target == pt->data) {
					cout << "Search : " << target << " , found : " << pt->data
							<< endl;
					return pt;
				} else
					pt = pt->next;
			}
			if (pt == NULL)
				cout << "Search : " << target << " , NOT FOUND";
		}
		return NULL;
	}

	//remove all node has value data
	void remove(int data) {
		if (pHead == NULL)
			return;
		if (data == pHead->data) {
			Node* p = pHead;
			pHead = pHead->next;
			delete p;
			//recursive call
			remove(data);
		}

		Node *ptPre = pHead;
		Node *pt = ptPre->next;

		while (pt != NULL) {
			if (data == pt->data) {
				Node* ptNext = pt->next;
				ptPre->next = ptNext;
				delete pt;
				pt = ptNext;
			} else {
				pt = pt->next;
				ptPre = ptPre->next;
			}
		}

	}

	//add an addLast method, add element to end of list
	void pospend(int data) {
		Node *pNew = new Node();
		pNew->data = data;
		pNew->next = NULL;
		if (pHead == NULL)
			pHead = pNew;
		else {
			Node* pt = pHead;
			while (pt->next != NULL)
				pt = pt->next;
			pt->next = pNew;
		}

		pNew = NULL;
	}

	// None Pointer -> CORE DUMP error !!!!!!!!
	void extend(SingleLinkedList list) {

		Node* ptrA = pHead;
		Node* ptrB = list.pHead;

		if (ptrB == NULL)
			return;
		else {

			//move ptrA to last node
			while (ptrA->next != NULL)
				ptrA = ptrA->next;

			//begin extend
			while (ptrB != NULL) {

				Node *ptr = new Node();
				ptr->next = NULL;
				ptr->data = ptrB->data;

				ptrA->next = ptr;
				ptrA = ptr;

				ptrB = ptrB->next;
			}
		}
	}

	// Using pointer -> NO ERROR !
	void extends(SingleLinkedList *other) {
		Node* ptrA = this->pHead;
		Node* ptrB = other->pHead;

		if (ptrB == NULL)
			return;
		else {

			//move ptrA to last node
			while (ptrA->next != NULL)
				ptrA = ptrA->next;

			//begin extend
			while (ptrB != NULL) {

				Node *ptr = new Node();
				ptr->next = NULL;
				ptr->data = ptrB->data;

				ptrA->next = ptr;
				ptrA = ptr;

				ptrB = ptrB->next;
			}
		}
	}

	// addictional destructor method
	~SingleLinkedList() {
		if (pHead == NULL)
			return;
		else {
			Node *pt = pHead;
			while (pt != NULL) {
				pHead = pt->next;
				delete pt;
				pt = pHead;
			}
		}
	}
};

// * 					MAIN FUNCTION FOR TESTING

/*int main() {
 cout << "BEGIN TEST : " << endl;

 SingleLinkedList L1;
 L1.prepend(7);
 L1.prepend(8);
 L1.prepend(4);
 L1.prepend(13);
 L1.prepend(10);
 L1.prepend(7);
 L1.prepend(5);
 L1.prepend(6);
 L1.prepend(9);
 L1.prepend(1);

 L1.display();

 // 					Test Insert Method

 L1.insert(99, 0);
 L1.display();

 // 					Test Search Method

 Node* n1 = L1.search(4);
 Node* n2 = L1.search(9999);

 if (n1 != NULL)
 n1 = NULL;
 if (n2 != NULL)
 n2 = NULL;
 cout << "\n\n";

 //					Test Remove Method

 SingleLinkedList L2;
 L2.prepend(3);
 L2.prepend(3);
 L2.prepend(7);
 L2.prepend(3);
 L2.prepend(8);
 L2.prepend(4);
 L2.prepend(3);
 L2.prepend(3);
 L2.prepend(13);
 L2.prepend(10);
 L2.prepend(7);
 L2.prepend(2);
 L2.prepend(3);
 L2.prepend(3);
 L2.prepend(3);
 L2.prepend(1);
 L2.prepend(3);
 cout << endl << "L2 before : " << endl;
 L2.display();
 cout << "Remove all data = 3 : " << endl;
 L2.remove(3);
 L2.display();
 L2.~SingleLinkedList();

 //					Test Method Extend

 SingleLinkedList LA;
 LA.prepend(3);
 LA.prepend(2);
 LA.prepend(1);

 SingleLinkedList LB;
 LB.prepend(5);
 LB.prepend(4);
 LB.prepend(6);
 LB.prepend(8);

 cout << "\n\nBefore Merge : " << endl;
 cout << "LA : " << endl;
 LA.display();
 cout << "LB : " << endl;
 LB.display();
 cout << "After merge : " << endl;
 // if LA.extend(LB) => core dump ?????
 LA.extends(&LB);
 cout << "LA: " << endl;
 LA.display();
 cout << "LB : " << endl;
 LB.display();

 // Call Destructors
 LA.~SingleLinkedList();
 LB.~SingleLinkedList();

 return 0;
 }*/

